POJ 2482 Stars in Your Window(扫描线、线段树)

题意:

$给定N\le 10^4个星星,每个有权值1\le w_i\le 100$
$现有W\times H的矩形,问能严格框住的星星最大权值和是多少$

分析:

$考虑把问题转化一下,先不管严格框住,考虑极限情况,一个星星位于左下角$
$那么就可以得到框住它的矩形是(x, y),(x+w, y+h)了$
$问题就转化成了类似于矩形面积并的问题,不过这里是求最大值$
$之后扫描线一波、线段树区间更新一波就好了$
$对于严格的情况,闭区间,可以把y+h变成y+h-1,w+h变成w+h-1$
$但是扫描线的时候要注意,因为是闭区间了,所以当重合的时候,要先添加再删除$
$当然扫描线每次都要注意这个的。。$
$嘛,只有查询maxv[1],写个标记永久化偷懒不用pushDown$
$时间复杂度O(nlogn)$

$代码:$

//
//  Created by TaoSama on 2016-08-24
//  Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e4 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

typedef long long LL;
LL x[N], y[N], r[N];
LL maxv[N << 3], addv[N << 3];

void update(int L, int R, int v, int l, int r, int rt) {
    if(L <= l && r <= R) {
        maxv[rt] += v;
        addv[rt] += v;
        return ;
    }
    int m = l + r >> 1;
    if(L <= m) update(L, R, v, l, m, rt << 1);
    if(R > m) update(L, R, v, m + 1, r, rt << 1 | 1);
    maxv[rt] = max(maxv[rt << 1], maxv[rt << 1 | 1]) + addv[rt];
}

int n, w, h;

#define y1 fddsfsdfds
struct Line {
    LL x, d, y1, y2;
    Line() {}
    Line(LL x, LL d, LL y1, LL y2): x(x), d(d), y1(y1), y2(y2) {}
    bool operator<(const Line& l) const {
        if(x == l.x) return d < l.d;
        return x < l.x;
    }
};

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
//  freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(scanf("%d%d%d", &n, &w, &h) == 3) {
        vector<LL> ys;
        for(int i = 1; i <= n; ++i) {
            scanf("%lld%lld%lld", x + i, y + i, r + i);
            ys.push_back(y[i]);
            ys.push_back(y[i] + h - 1);
        }
        sort(ys.begin(), ys.end());
        ys.resize(unique(ys.begin(), ys.end()) - ys.begin());

        vector<Line> events;
        for(int i = 1; i <= n; ++i) {
            LL y1 = lower_bound(ys.begin(), ys.end(), y[i]) - ys.begin() + 1;
            LL y2 = lower_bound(ys.begin(), ys.end(), y[i] + h - 1) - ys.begin() + 1;
            events.push_back(Line(x[i], -r[i], y1, y2)); //+ first
            events.push_back(Line(x[i] + w - 1, r[i], y1, y2)); 
        }
        sort(events.begin(), events.end());

        memset(maxv, 0, sizeof maxv);
        memset(addv, 0, sizeof addv);

        LL ans = 0;
        for(int i = 0; i < events.size(); ++i) {
            Line& e = events[i];
            LL d = -e.d, y1 = e.y1, y2 = e.y2;
            update(y1, y2, d, 1, ys.size(), 1);
//            pr(e.x); pr(d);pr(y1);pr(y2);prln(maxv[1]);
            ans = max(ans, maxv[1]);
        }
        printf("%lld\n", ans);
    }

    return 0;
}